package formal.string;

/**
 * @author DengYuan2
 * @create 2021-02-02 20:22
 */
public class M_647 {
    public static void main(String[] args) {
        String s = "aaa";
        int res = countSubstrings2(s);
        System.out.println(res);
    }

    /**
     * 我的写法-超级慢
     *
     * @param s
     * @return
     */
    public static int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                count += helper(s.substring(i, j));
            }
        }
        return count;
    }

    /**
     * 判断是否为回文
     *
     * @param s
     * @return
     */
    public static int helper(String s) {
        if (s.length() == 1) {
            return 1;
        }
        char[] c = s.toCharArray();
        int l = 0;
        int r = c.length - 1;
        while (l <= r) {
            if (c[l] != c[r]) {
                return 0;
            }
            l++;
            r--;
        }
        return 1;
    }

    /**
     * 大神的写法-从字符串的某一位开始，尝试着去扩展子字符串
     * 官方也是这个意思，但这个比较好明白
     *
     * @param s
     * @return
     */
    public static int cnt = 0;

    public static int countSubstrings2(String s) {
        for (int i = 0; i < s.length(); i++) {
            extend(s, i, i);
            extend(s, i, i + 1);
        }
        return cnt;

    }

    public static void extend(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
            cnt++;
        }
    }

    /**
     * 动态规划法-不如上面的快
     *
     * @param s
     * @return
     */
    public static int countSubstrings3(String s) {
        int cnt = 0;
        boolean[][] round = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || round[j + 1][i - 1])) {
                    round[j][i] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}
